#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *right;
    TreeNode *left;
};
void preOrderTraverase(TreeNode *t);
void insertTreeNode(TreeNode **t, int data);


//-------------核心代码---------------
vector<int> levelOrder(TreeNode* t)
{
    vector<int>res;
    
    //先判断 再处理
    if(! t)
        return res;

    queue<TreeNode*> qu;
    // 首节点入队
    qu.push(t);

    while(! qu.empty()) //当队列中不为空时
    {
        TreeNode *root = qu.front();
        if(root->left != NULL)
            qu.push(root->left);
        if(root->right != NULL)
            qu.push(root->right);

        qu.pop();
        res.push_back(root->val);
    }
    return res;
}



int main()
{
    TreeNode *root = NULL;

    int n = 7;
    //    cin>>n; //结点个数

    while(n--)
    {
        int data;
        cin>>data;
        insertTreeNode(&root,data);
    }

    cout<<"=================="<<endl;

    vector<int> vi;
    vi = levelOrder(root); //层序输出的结果
    for(auto i:vi)
        cout<<i<<" ";

    return 0;
}

//有序递归插入
void insertTreeNode(TreeNode **t, int data)
{
    if((*t) == NULL)
    {
        (*t) = new TreeNode;
        (*t)->val = data;
        (*t)->left = (*t)->right = NULL;
    }
    else if(data > (*t)->val)
    {
        insertTreeNode(&((*t)->right),data);
    }
    else
        insertTreeNode(&((*t)->left),data);
}
